from typing import List


class Solution:
    # dp 方法一：动态规划
    # def findLength(self, A: List[int], B: List[int]) -> int:
    #     m = len(A)
    #     n = len(B)
    #     ans = 0
    #     #
    #     dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    #     for i in range(1, m + 1):
    #         for j in range(1, n + 1):
    #             if A[i - 1] == B[j - 1]:
    #                 dp[i][j] = dp[i - 1][j - 1] + 1
    #                 ans = max(ans, dp[i][j])
    #     return ans

    # sw 方法二：滑动窗口
    # def findLength2(self, A: List[int], B: List[int]) -> int:
    #     def maxSubLength(startA: int, startB: int, length: int):
    #         res = temp = 0
    #         for i in range(length):
    #             if A[startA + i] == B[startB + i]:
    #                 temp += 1
    #                 res = max(temp, res)
    #             else:
    #                 temp = 0
    #             print(startA, startB, length, '  ', res)
    #         return res
    #
    #     m = len(A)
    #     n = len(B)
    #     ans = 0
    #     for i in range(m):
    #         length = min(m - i, n)
    #         if ans >= length:
    #             break
    #         ans = max(ans, maxSubLength(i, 0, length))
    #     for i in range(n):
    #         length = min(m, n - i)
    #         if ans >= length:
    #             break
    #         ans = max(ans, maxSubLength(0, i, length))
    #     return ans
    def findLength3(self, A: List[int], B: List[int]) -> int:
        base, mod = 113, 10 ** 9 + 9

        def check(length: int) -> bool:
            hashA = 0
            for i in range(length):
                hashA = (hashA * base + A[i]) % mod
            bucketA = {hashA}
            mult = pow(base, length - 1, mod)
            for i in range(length, len(A)):
                hashA = ((hashA - A[i - length] * mult) * base + A[i]) % mod
                bucketA.add(hashA)

            hashB = 0
            for i in range(length):
                hashB = (hashB * base + B[i]) % mod
            if hashB in bucketA:
                return True
            for i in range(length, len(B)):
                hashB = ((hashB - B[i - length] * mult) * base + B[i]) % mod
                if hashB in bucketA:
                    return True

            return False

        left, right = 0, min(len(A), len(B))
        ans = 0
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        return ans


if __name__ == "__main__":
    mySol = Solution()
    al = [1, 2, 3, 2, 1, 0, 1]
    bl = [3, 2, 1, 0, 1, 4, 7]
    # al = [0, 0, 0, 0, 1]
    # bl = [1, 0, 0, 0, 0]
    print('feedback:', mySol.findLength3(al, bl))
